package model;

import java.util.Stack;

public class CalculatorGraph {

public static int INFINITY = Integer.MAX_VALUE;
	
	private Vertex[] vertex;
	private Vertex[] V; 
	
	public CalculatorGraph(Vertex[] nos) {
		this.setNos(nos);
	}
	
	public Vertex[] getVertex() {
		return this.vertex;
	}
	
	public void setNos(Vertex[] v) {
		this.vertex = v;
	}
	
	
	public boolean emN(Vertex v) {
		for (int i = 0; i < V.length; i++) {
			if (v.compareTo(V[i]) == 0)
				return true;
		}
		
		return false;
	}
	
	public Vertex[] menorCaminho(Vertex home, Vertex fate) {
		int i = 0, j = 0;
		Vertex menor = null, atual = null; 
		
		V = new Vertex[vertex.length];
		V[j++] = home;
		
		for (i = 0; i < vertex.length; i++) {
			vertex[i].setCust(INFINITY);
			vertex[i].setPrevious(null);
		}
		
		atual = home;
		
		atual.setCust(0); 
		
//		Vertex[] vizinhos = atual.getVizinhos();		
//		if (vizinhos == null)
//			return null;		
//		for (i = 0; i < vizinhos.length; i++)
//			vizinhos[i].setPrevious(atual);
		
		while (atual.compareTo(fate) != 0) {
			menor = null;
			
			for (i = 0; i < vertex.length; i++) {
				if (!emN(vertex[i])) {
					if (menor == null)
						menor = vertex[i];
					
					if (atual.getCust() + atual.getWeight(vertex[i]) < vertex[i].getCust()) {
						if (atual.getWeight(vertex[i]) < INFINITY) {
							vertex[i].setCust(atual.getCust() + atual.getWeight(vertex[i]));
							
							if (atual.getWeight(vertex[i]) < INFINITY)
								vertex[i].setPrevious(atual);
						}
					}
					
					if (vertex[i].getCust() < menor.getCust()) {
						menor = vertex[i];
					}
				}
			}
			
			atual = menor;
			V[j++] = atual;
		}
		
		Stack pilha = new Stack();
		Vertex[] retorno = new Vertex[V.length];
		atual = V[j - 1];
		i = 0;
		
		while (atual != null) {
			pilha.push(atual);
			atual = atual.getPrevious();
		}
		
		j = pilha.size();
		for (i = 0; i < j; i++) 
			retorno[i] = (Vertex)pilha.pop();
		
		java.util.List<Vertex> vertexs = java.util.Arrays.asList( retorno );
		java.util.List<Vertex> vretorno = new java.util.ArrayList<Vertex>();
		for (Vertex v : vertexs) {
			if ( v != null )
				vretorno.add(v);
		}
		
		return vretorno.toArray( new Vertex[ vretorno.size() ] );
	}
	
	
}
